package hot100;

import org.junit.Test;

import java.util.HashSet;
import java.util.Set;

public class MergeKLists {
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        //创建一组指针
        ListNode[] ptr = new ListNode[lists.length];
        for (int i = 0; i < lists.length; i++) {
            ptr[i] = lists[i];
        }
        Set<Integer> finishedListIndex = new HashSet<>();//存放已经遍历完的链表的索引
        ListNode preHead = new ListNode(-1);
        ListNode tail = preHead;
        while (finishedListIndex.size() < lists.length) {
            //遍历指针列表
            int min = 0;
            for (int i = 0; i < ptr.length; i++) {
                if (finishedListIndex.contains(i)) continue;//该链表已遍历完
                if (ptr[min] == null) min = i;
                else {
                    if (ptr[i] != null && ptr[i].val < ptr[min].val) min = i;
                }
            }
            //最小值已确定，插入合并链表
            if (ptr[min] == null) break;//所有指针都为空，链表全遍历完，或者说链表全为空链表
            tail.next = ptr[min];
            tail = ptr[min];
            ptr[min] = ptr[min].next;

            if (ptr[min] == null) finishedListIndex.add(min);
        }

        return preHead.next;
    }

    @Test
    public void test() {
        //[[1,4,5],[1,3,4],[2,6]]
        ListNode[] in = new ListNode[3];
        in[0] = constructList(new int[]{1,4,5});
        in[1] = constructList(new int[]{1,3,4});
        in[2] = constructList(new int[]{2,6});

        ListNode listNode = mergeKLists(in);
        printList(listNode);
    }

    public ListNode constructList(int[] arr) {
        ListNode preHead = new ListNode(-1);
        ListNode tail = preHead;
        for (int num : arr) {
            ListNode node = new ListNode(num);
            tail.next = node;
            tail = node;
        }

        return preHead.next;
    }

    public void printList(ListNode head) {
        ListNode p = head;
        while (p != null) {
            System.out.print(p.val + " ");
            p = p.next;
        }
    }
}
